package nowCoder;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
 * 
 * @author Ghost
 *
 */
public class GetLeastNumbers_Solution {
	public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
		
		ArrayList<Integer> rstArrayList = new ArrayList<Integer>(); 
		if(input==null || input.length==0 || k<0)
			return rstArrayList;
		if(input.length<k){
			for(int i:input)
				rstArrayList.add(i);
			return rstArrayList;
		}
		
		PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(k, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o2-o1; 
			}
		});
		
		
		for(int i=0;i<k;i++){
			pQueue.offer(input[i]);
		}
		for(int i=k;i<input.length;i++){
			if(input[i]<pQueue.peek()){
				pQueue.poll();
				pQueue.offer(input[i]);
			}
		}
		rstArrayList = new ArrayList<Integer>(k); 
		while(!pQueue.isEmpty()){
			rstArrayList.add(pQueue.poll());
		}
		return rstArrayList;
	}
	public static void main(String[] args){
		GetLeastNumbers_Solution getLeastNumbers_Solution=  new GetLeastNumbers_Solution();
		int[] input = {};
		int k=5;
		System.out.println(getLeastNumbers_Solution.GetLeastNumbers_Solution(null, k));
	}
}
